// https://leetcode.cn/problems/stickers-to-spell-word/description/
#include <bits/stdc++.h>
using namespace std;

long long myhash(int cnt[]) {
    long long ret = 0, base = 499;
    long long mod = 1e9 + 7;
    for (int i = 0; i < 26; i++) {
        ret = (ret * base % mod + (i + 1) * cnt[i]) % mod;
    }
    return ret;
}

int minStickers(vector<string>& s, string t) {
    vector<vector<int>> cnt(s.size(), vector<int>(26));
    vector<bool> flag(26);
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < s[i].length(); j++) {
            cnt[i][s[i][j] - 'a']++;
            flag[s[i][j] - 'a'] = true;
        }
    }   
    struct Node {
        int d;
        int need[26];
    };
    deque<Node> que;
    Node start; start.d = 0;
    for (int i = 0; i < t.size(); i++) {
        start.need[t[i] - 'a']++;
        if (!flag[t[i] - 'a']) return -1;
    }
    que.push_back(start);
    set<long long> st;
    st.insert(myhash(start.need));
    while (!que.empty()) {
        bool flag = true;
        Node now = que.front(); que.pop_front();
        for (int j = 0; j < 26; j++) {
            if (now.need[j] > 0) {
                flag = false;
            }
        }
        if (flag) {
            return now.d;
        }
        for (int i = 0; i < s.size(); i++) {
            Node next; next.d = now.d + 1;
            for (int j = 0; j < 26; j++) {
                next.need[j] = now.need[j] - cnt[i][j];
            }
            if (!st.count(myhash(next.need)))
                que.push_back(next);
        }
    }
    return -1;
}

int main() {

    return 0;
}